package codeRandomThoughts.Test654最大二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.util.LinkedList;

public class Solution2 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTreeWithIndex(nums, 0, nums.length - 1);
    }

    //左闭右闭
    public TreeNode constructMaximumBinaryTreeWithIndex(int[] nums, int begin, int end) {
        if (begin > end) {
            return null;
        }

        //求最大值在数组中的位置
        int maxVal = nums[begin];
        int maxIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }

        TreeNode root = new TreeNode(maxVal);
        root.left = constructMaximumBinaryTreeWithIndex(nums, begin, maxIndex - 1);
        root.right = constructMaximumBinaryTreeWithIndex(nums, maxIndex + 1, end);
        return root;
    }
}
